백준 2096번
오늘 풀어본 문제는 백준의 2096번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
$N$ 줄에 $0$ 이상 $9$ 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.
먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.
별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.
입력
첫째 줄에 $N$ $(1 \leq N \leq 100,000)$ 이 주어진다. 다음 $N$ 개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 $0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9$ 중의 하나가 된다.
출력
첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.
풀이과정
1번째 시도
문제를 보고 DP를 이용하는 문제라는 것을 알 수 있었다. 이전 행에서 건너올 수 있는 칸들까지의 최소 점수들 중의 최소값와 최대 점수들 중의 최댓값을 각 칸의 점수와 더해 저장해 나가는 방식으로 구현하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
vector<int> board[3];
vector<pii> min_max[3];
int main(void) {
int N;
cin >> N;
board[0].resize(N);
board[1].resize(N);
board[2].resize(N);
min_max[0].resize(N);
min_max[1].resize(N);
min_max[2].resize(N);
for (int i = 0; i < N; i++) {
cin >> board[0][i] >> board[1][i] >> board[2][i];
min_max[0][i] = make_pair(board[0][i], board[0][i]);
min_max[1][i] = make_pair(board[1][i], board[1][i]);
min_max[2][i] = make_pair(board[2][i], board[2][i]);
}
for (int i = 0; i < 3; i++) {
}
for (int i = 1; i < N; i++) {
min_max[0][i].first += min(min_max[0][i - 1].first, min_max[1][i - 1].first);
min_max[0][i].second += max(min_max[0][i - 1].second, min_max[1][i - 1].second);
min_max[1][i].first += min({ min_max[0][i - 1].first, min_max[1][i - 1].first, min_max[2][i - 1].first });
min_max[1][i].second += max({ min_max[0][i - 1].second, min_max[1][i - 1].second, min_max[2][i - 1].second });
min_max[2][i].first += min(min_max[1][i - 1].first, min_max[2][i - 1].first);
min_max[2][i].second += max(min_max[1][i - 1].second, min_max[2][i - 1].second);
}
cout << max({ min_max[0][N - 1].second, min_max[1][N - 1].second, min_max[2][N - 1].second }) << " " << min({ min_max[0][N - 1].first, min_max[1][N - 1].first, min_max[2][N - 1].first });
return 0;
}
실행 결과 ‘메모리 초과’가 발생하였다.
2번째 시도
문제를 다시 읽어보니, 메모리 제한이 4 MB 로 걸려있는 것을 확인할 수 있었다. 다른 문제들 같으면 훨씬 큰 메모리를 사용할 수 있었겠지만, 이 문제는 의도적으로 메모리 사용량을 제한하고 있었다.
메모리 사용량을 줄이는 것은 어렵지 않았다. 한 번 지나간 행에 대한 정보는 다시 조회할 필요도, 사용할 필요도 없었기 떄문에 현재 행의 정보와 이전 행의 정보만 저장하도록 하여 현재 행과 이전 행을 한 칸씩 내려가며 업데이트 하도록 하였고, 마지막에 현재 행의 정보를 이용하여 결과를 계산하도록 하였다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
pii previous[3];
pii current[3];
int main(void) {
int N;
cin >> N;
for (int i = 0; i < 3; i++) {
cin >> previous[i].first;
previous[i].second = previous[i].first;
current[i] = previous[i];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < 3; j++) {
cin >> current[j].first;
current[j].second = current[j].first;
}
current[0].first += min(previous[0].first, previous[1].first);
current[0].second += max(previous[0].second, previous[1].second);
current[1].first += min({ previous[0].first, previous[1].first, previous[2].first });
current[1].second += max({ previous[0].second, previous[1].second, previous[2].second });
current[2].first += min(previous[1].first, previous[2].first);
current[2].second += max(previous[1].second, previous[2].second);
for (int j = 0; j < 3; j++) {
previous[j] = current[j];
}
}
cout << max({ current[0].second, current[1].second, current[2].second }) << " " << min({ current[0].first, current[1].first, current[2].first });
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
쉬운 문제였다고 생각하며 제출했는데 ‘메모리 초과’가 떠서 당황스러웠다. 이후에 답안을 수정하는 과정이 어렵지는 않았지만, 평소에 내가 DP 문제를 풀 때 최적화를 별로 신경쓰고 있지 않아왔다는 것을 알 수 있었다. 앞으로는 좀 더 신경써서 한 번에 딱 맞출 수 있도록 해보겠다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/2096